def partition (arr, begin, end):
    pivot = arr[end]                # 轴
    pointer = begin                 # 指针，指针前的数字都比轴小
    # 遍历数组
    for i in range(begin, end):
        # 利用指针把比轴小的数交换到指针前面
        if arr[i] < pivot:
            arr[i], arr[pointer] = arr[pointer], arr[i]
            pointer += 1
    # 把轴交换到指针处
    arr[end], arr[pointer] = arr[pointer], arr[end]
    # print(pivot, arr)
    return pointer

def quicksort(arr, begin, end):
    if begin < end: # 边界条件，子数组长度不为零
        pointer = partition(arr,begin,end)
        # 分治
        quicksort(arr, begin, pointer-1)
        quicksort(arr, pointer+1, end)

if __name__ == '__main__':
    import random
    arr = list(range(8))
    random.shuffle(arr)
    quicksort(arr, 0, len(arr)-1)
